LinuxCon Experience

13 – 15 October 2014, three great days.

I have never been to a conference before and the LinuxCon + CloudOpen + ELC Europe experience made me want to go to Linux related conferences in the future.

I arrived Friday afternoon in Dusseldorf, so I had time to visit the city before the start of the conference. It was a relaxing weekend visiting a nice city, with very big servings of great food :-)

Monday

The first day was the most full of emotions. After registration and the morning keynotes, I went with my friends at lunch where I didn’t eat anything because I was nervous for the next two presentations:

• “Tutorial: Getting Started with Coccinelle“. Julia Lawall asked me and Himangi (another intern at OPW this round) to come and answer the questions of the people who are participating in the tutorial. I got rid of those emotions immediately after I met Julia and the presentation started. Every time someone in the room had a problem/question, one of us would go at that person and helped him/her. At the end, Julia said that this was the best version of the tutorial ever. So, it was an interesting experience and I am glad that Julia asked me to participate.
• “Kernel Internship Report (OPW)“. After the Coccinelle workshop, I went directly to the next presentation where I had to sustain my first public presentation. Of course, the emotions were back :-) I met Sarah who started the presentation by giving some statistics regarding the OPW internships (like number of patches, lines added/removed, etc.). At some point, I had to do a lightning-talk about my project and it was a nice experience because I managed to control my emotions and the feedback after my presentation was good. At the end of the presentation, we took some photos with Sarah and the interns.

After this presentation, I met my mentor, Paul E. McKenney, for the first time in person on the hallway and we talked about many things. Also, I attended the VIP dinner where I talked with Sarah, Greg, Michael Opdenacker from Free Electrons (I’ve met him at the Coccinelle tutorial) and interns from OPW.

Tuesday

The second day was also a full day. I attended various interesting presentations like “Linux Performance Tools” by Brendan Gregg or “Building a Secure, Thrustworthy and Freedom-Respecting Linux Platform” by Matthew Garrett.

For dinner, Sarah organised an OPW dinner. It was really exciting, I had time to talk with my mentor about a lot of things and I had a really great time. I was surprised that my mentor heard about George Enescu, a Romanian violinist, pianist and one of the greatest composers of the 20th century, who was born in my hometown :-)

Wednesday

The last day was a really good day for presentations, I liked all of the ones where I went. The most interesting were:

• “Ftrace Kernel Hooks: More than Just Tracing” by Steven Rostedt. I like technical presentations and this was one of them. It was about different obstacles and possible solutions in the implementation of ftrace.
• “How to Design a Linux Kernel API” by Michael Kerrisck. Michael Kerrisck is the author of “The Linux Programming Interface” a book which I learned from at the Operating Systems course and it was nice attending his talk and hear some advices from him.
• “Linux Kernel Tinification” by Josh Triplett. Another technical and interesting presentation. I was not familiar with the tinification approach and I found out new things in this way. I am glad that I had the chance to meet Josh at the OPW dinner. By the way, Linux Kernel Tinification is a project this round at the OPW which will start in December.

After all the presentations, I went to the closing reception where I spent all the time with my mentor and met many people.

Overall, the conference was a great experience. I met a lot of people, I did my first public presentation and I find out about new things by attending the presentations.

Also, I am happy that I met my mentor and other people from the OPW team.

I really liked the community, the nice people and I can’t wait for the next LinuxCon!

The end of the internship

Last week the official days of the internship ended. It was a challenging and very interesting experience for me.

A short overview of the internship:

The beginning was the hardest part of the internship. I had to accommodate with both RCU notions, Coccinelle syntax and on top of this I had to take my exams at the university. The first weeks I struggled to figure out the Coccinelle syntax and try to use it for my tasks. Also, I was reading and talking with my mentor about RCU in order to know its API and the way it works so I can apply this understanding in solving problems.

Once I began being friends with Coccinelle everything became a little easier.

The main steps I followed in solving the tasks were:
– think about the task and discuss about it with my mentor
– write a simple Coccinelle script and step-by-step make it more efficient (where the task permitted;
some of the scripts made the changes right when the script was applied on the files, others only highlighted cases and after that, I would analyze the output and decide if I should make a change or not)
– discuss with my mentor my observations and possible fixes for the bugs

Unfortunately (for me), for some tasks I didn’t find many bugs as I wanted (a chance to send more patches and contribute more to Linux kernel 🙂 ). Anyway I learned a lot by analyzing all those cases even though only a few of them transformed into patches. Many of those cases were tricky ones and I think that was a good learning experience for me, trying to see if there really was a problem or not.

I still have work in progress and patches to send. Also, I wait for answers at many patches already sent. I will come up with a post with summaries for every task after I have all the answers.

Some lessons learned:
– good understanding of RCU
– intermediate user of Coccinelle
– analyze code written by other people
– you don’t have to automatize something if there is nothing to automatize
For sure, there are more, but these are in my mind right now.

Many thanks to my mentor, Paul E. McKenney, for all the advice for the project and in general, the quick answers and for all the help that he offered me. Thanks to Julia Lawall because every time when I had a Coccinelle problem she made time and helped me. Also, I want to thank the people from OPW. All of them are very nice and eager to help anybody!

In the end, I can say that my work for Linux kernel will continue for sure.

I can’t wait for LinuxCon Europe in October where I will talk about my project and meet people from OPW.
See you around!

Searching for bugs

In this post, I will talk about another task I’ve been working on:
“Making use of an RCU-protected pointer after passing it to call_rcu() or similar function (“call_rcu_bh()”, “call_rcu_sched()”, “call_srcu()”)”.

First, let’s see what “call_rcu()” does.
The write-side RCU primitives allow the caller to defer an action like deleting a pointer until all pre-existing RCU critical sections have finished execution (meaning that the pointer isn’t used anymore and it is safe to remove it).
RCU’s API provides two ways for this:
– “synchronize_kernel()”
– “call_rcu()”

When “synchronize_kernel()” is called it blocks until the end of all pre-existing read-side RCU critical sections.
But, in some cases, you don’t want to wait and it might be inefficient. So, instead of “synchronize_kernel()” you use “call_rcu()”.
“call_rcu()” invokes the callback function (the second parameter) after all pre-existing RCU critical section have completed execution.

Why do we need “call_rcu_bh()”, “call_rcu_sched()” and “call_srcu()”?
That is because of RCU’s flavors:

RCU-sched is needed for waiting for hardware interrupts.
RCU-bh is needed in cases related with denial of service attacks.
SRCU permits sleeping in RCU read-side critical sections.

The principal thing to do in order to solve this task is to identify when the variable goes dead.
Examples:

/* BUG */
call_rcu(&p->head, func);
/* p doesn’t exist anymore */
p->a = 1;

/* OK */
call_rcu(&p->head, func);
/* we are using another pointer that is stored in the same pointer variable */
p = kmalloc(sizeof(p), GFP_KERNEL);
p->a = 1;

I started with this Coccinelle semantic patch which looks for a “call_rcu()” call and sees if after that call the pointer is used.

@@
identifier f, p;
@@

f(…) {
… when any
* call_rcu((<+…p…+>), …);
… when any
* (<+…p…+>)
… when any
}

For the similar functions I replaced “call_rcu()” with the function of interest.
I didn’t find bugs using this approach, but I will show you some cases that at first sight might seem bugs.

– file “kernel/rcu/rcutorture.c”:

rcu_read_lock(); /* Make it impossible to finish a grace period. */
call_rcu(&rh1, rcu_torture_leak_cb); /* Start grace period. */
local_irq_disable(); /* Make it harder to start a new grace period. */
call_rcu(&rh2, rcu_torture_leak_cb);
call_rcu(&rh2, rcu_torture_err_cb); /* Duplicate callback. */
local_irq_enable();
rcu_read_unlock();

This case (the two calls with rh2) is OK because it is for debugging purposes.

– file “net/bridge/br_multicast.c”:

if (!old)
    goto out;

…

call_rcu_bh(&mdb->rcu, br_mdb_free);

out:
    rcu_assign_pointer(*mdbp, mdb);

A few lines before the “call_rcu_bh()” call there is a “goto out” so this means that it doesn’t get to the call when the if condition is successful.

– file “arch/powerpc/mm/hugetlbpage.c”:

call_rcu_sched(&(*batchp)->rcu, hugepd_free_rcu_callback);
*batchp = NULL;

Everything OK, it just uses the same pointer variable.

The first approach was the normal one and the simpler one to start with, but every case that I found was OK.

The second approach is the following:
first step: find assignments like this one: “g = call_rcu(…)” (g is a global variable).
second step: find the functions where these assignments are
third step: find the functions where the functions found at the second step are called
fourth step: see if in the functions found at the third step the protected pointer is used in a bad way.

The Coccinelle script used for this:

@ locally @
identifier l;
type t;
position p;
@@

t l;
… when any
call_rcu@p((<+…p…+>), …);

@ globally @
identifier fn;
identifier g != locally.l;
position p2 != locally.p;
@@

fn(…) {
… when any
call_rcu@p2((<+…p…+>), …);
… when any
}

@ other_func @
identifier globally.fn, ff;
@@

ff(…) {
… when any
* fn(…)
… when any
}

In the first rule, I look for uses of “call_rcu()” where it assigns to a local variable. In the second rule, I exclude the cases where the variable might be local (using positions). In the third rule, I search for the calls to the functions found in the second rule.

In a few days I will tell you about two interesting cases that I found using this script and the solutions (or if they need a solution).

rcu_assign_pointer()

The time passes so quickly and all the interns have only a few weeks before the end of this internship. Anyway, my work for Linux kernel will continue for sure even after OPW.

In this post I will present two Coccinelle scripts for one of the tasks that I talked about in the previous posts (the one with the “rcu_assign_pointer()” and its replacement with “RCU_INIT_POINTER()” or not).

The following Coccinelle script says when we need to keep the “rcu_assign_pointer()” call (and not replacing it with “RCU_INIT_POINTER()”) for the case when the value that will be assigned to the pointer is updated before the call (by a call to another function that might update it or in other ways):

/* The first rule finds different ways in which the value is updated before the call */

@ value_updated @
identifier upd;
identifier v;
@@
(
 (<+…v…+>) = …;
|
\(memset\|memcpy\)((<+…v…+>), …);
|
upd(v, …);
|
atomic_inc((<+…v…+>));
|
++(<+…v…+>);
)
… when any
rcu_assign_pointer(…, v);

/* This rule sees if the update function found in the previous rule updates the parameter */

@ update_func @
identifier value_updated.upd;
identifier fv;
type t;
@@

upd(t fv,…) {
… when any
(
 (<+…fv…+>) = …;
|
\(memset\|memcpy\)((<+…fv…+>), …);
|
atomic_inc((<+…fv…+>));
)
… when any
}

/* The rule ignores this case because this is a case where we actually can use “RCU_INIT_POINTER()” according to “RCU_INIT_POINTER()’s” block comment, section 3a. */

@ ignore @
identifier value_updated.v;
@@

v = rcu_dereference(…);
… when != rcu_dereference(…);
      when != v = …;
      when != \(memcpy\|memset\)(…);
rcu_assign_pointer(…, v);

/* This rule highlights the pairs “update the value – call of “rcu_assign_pointer()”” because I want to see only these cases and not other uses of “rcu_assign_pointer()” that are not treated in this script */

@ match1 depends on !ignore @
identifier v;
@@

(
* (<+…v…+>) = …;
|
* \(memset\|memcpy\)((<+…v…+>), …);
|
* atomic_inc((<+…v…+>));
|
* ++(<+…v…+>);
)
… when any
* rcu_assign_pointer(…, v);

/* Also, this rule highlights the pairs “function that updates the value – call of “rcu_assign_pointer()”” */

@ print depends on update_func @
identifier v;
identifier value_updated.upd;
@@

* upd(v, …);
… when any
* rcu_assign_pointer(…, v);

 

Let’s see some examples:

-> for the file “block/blk-cgroup.c” the output is:

– blkg = radix_tree_lookup(&blkcg->blkg_tree, q->id);
if (blkg && blkg->q == q) {
if (update_hint) {
lockdep_assert_held(q->queue_lock);
– rcu_assign_pointer(blkcg->blkg_hint, blkg);

 

-> for the file “kernel/workqueue.c”:

– link_pwq(pwq);

old_pwq = rcu_access_pointer(wq->numa_pwq_tbl[node]);
– rcu_assign_pointer(wq->numa_pwq_tbl[node], pwq);

* the function “link_pwd()” updates the parameter “pwq”

-> for the file “drivers/infiniband/hw/qib/qib_qp.c”:

– atomic_inc(&qp->refcount);
spin_lock_irqsave(&dev->qpt_lock, flags);if (qp->ibqp.qp_num == 0)
– rcu_assign_pointer(ibp->qp0, qp);
else if (qp->ibqp.qp_num == 1)
– rcu_assign_pointer(ibp->qp1, qp);
else {
– qp->next = dev->qp_table[n];
– rcu_assign_pointer(dev->qp_table[n], qp);

 

Another Coccinelle semantic patch that actually replaces the function is:

/* “RCU_INIT_POINTER()’s” block comment, section 1 is used for the NULL part and the section 3a is used for “rcu_dereference_protected()” and “rtnl_dereference()” (which actually calls the previous one) */
@ match1 @
@@

– rcu_assign_pointer
+ RCU_INIT_POINTER
(…,
(
NULL
|
rcu_dereference_protected(…)
|
rtnl_dereference(…)
) )

/* Because there are cases where between a “rcu_dereference()” call and a “rcu_assign_pointer()” call can be updates of the value that interests us, we need to ignore them and replace only when the update is not happening */

@ match2 @
identifier v;
@@

v = rcu_dereference(…);
… when != rcu_dereference(…);
      when != v = …;
      when != \(memcpy\|memset\)(…);
(
– rcu_assign_pointer
+ RCU_INIT_POINTER
(…, v);
|
if(…) {
… when != v = …;
– rcu_assign_pointer
+ RCU_INIT_POINTER
(…, v);
… when != v = …;
}
)

 

Some output examples (or parts of examples):

-> for the file “block/genhd.c”:

part = rcu_dereference(ptbl->part[i]);if (part && sector_in_part(part, sector)) {

– rcu_assign_pointer(ptbl->last_lookup, part);
+ RCU_INIT_POINTER(ptbl->last_lookup, part);if (old_ptbl) {

– rcu_assign_pointer(old_ptbl->last_lookup, NULL);
+ RCU_INIT_POINTER(old_ptbl->last_lookup, NULL);

 

-> for the file “drivers/infiniband/ulp/ipoib/ipoib_main.c”:

– rcu_assign_pointer(*np,
+ RCU_INIT_POINTER(*np,
rcu_dereference_protected(neigh->hnext,
lockdep_is_held(&priv->lock)));

 

Also, I have some good news. I successfully ran the kernel with qemu with the help of my mentor 🙂

Coccinelle

In the past couple of weeks I concentrated on Coccinelle, learning its syntax and figure how to write my Coccinelle scripts to do what I want in order to complete my tasks.

Let’s see the cases promised in the previous post where “RCU_INIT_POINTER()” can be replaced with “rcu_assign_pointer()”. These are the cases from “RCU_INIT_POINTER()’s” block comment:

1. This use of RCU_INIT_POINTER() is NULLing out the pointer -or-

2. The caller has taken whatever steps are required to prevent RCU readers from concurrently accessing this pointer -or-

3. The referenced data structure has already been exposed to readers either at compile time or via rcu_assign_pointer() -and-

a. You have not made -any- reader-visible changes to this structure since then -or-

b. It is OK for readers accessing this structure from its new location to see the old state of the structure. (For example, the changes were to statistical counters or to other state where exact synchronization is not required.)

The first case is the most simpler and the Coccinelle semantic patch is very short and easy:

@@ expression E; @@

– rcu_assign_pointer(E, NULL)

+ RCU_INIT_POINTER(E, NULL)

I thought about how I can write a Coccinelle script to detect the next two cases and it was a bit hard to find particular cases that would be worth writing a Coccinelle script and automatize a specific case (that is because of the different cases where “rcu_assign_pointer()” is used). So, together with my mentor, we decided that I should be writing a Coccinelle script which detects when you should keep the call “rcu_assign_pointer()” instead.

Currently, I am trying to detect when the value that is going to be assigned to the pointer is updated before “rcu_assign_pointer()” because this is one common case where “RCU_INIT_POINTER()” isn’t needed. One difficult case is that I have to find the call of the function where “v” is a parameter and after that, to verify if “v” is updated in the code of that function:

function(…) {

…

func_that_might_update_v(v, …);

…

rcu_assign_pointer(p, v);

…

}

I will keep you updated and I am hoping that in the next few days I will complete what I have in my mind.

 

A week ago, I took a pause from the above task. I received an email from my mentor in which he offered me an extra task, if I wanted. The task consists of writing a Coccinelle script that detects use of “alloc_percpu()” that assigns to a global variable without either an “smp_mb()”, “smp_wmb()”, or “smp_store_release()”.

“alloc_percpu()” is a macro and it allocates one instance of the type given as a parameter for every processor on the system (all percpu areas are zeroed on allocation). There are cases where is the need for barriers to prevent one or more CPU’s to see garbage values.

I started by finding the calls “alloc_percpu()”. After that, I verified if the variable that the call assigns is a local or global variable. A variable which is not local, it is global. I used the metavariable type “position” offered by Coccinelle:

@ locally @
local idexpression l;
position p;
@@

(<+…l…+>) =@p alloc_percpu(…)

@ globally @
expression g;
position p != locally.p;
@@

g@p = alloc_percpu(…)

Practically, I located all local variables and after that, I excluded them in order to remain with the global ones.

I encountered problems when I tested because in some cases the output said that a certain variable was global when it was not. Even with this problem, during one online meeting with my mentor we realised that harder things are to come. The detection of the barrier and if that barrier is what we are looking for or not, is not easy and maybe not suitable for a Coccinelle script.

So, after a little talking, we decided to change the way in which we approach this problem. We know for sure that if the variable that “alloc_percpu()” assigns is updated after that call we need a barrier.

I will make a Coccinelle script that detects if a global variable that receives memory through the call “alloc_percpu()” is initialized after the allocation.

In a few days, I will come up with the final results for these tasks . Also, I will tell you about my adventure with qemu, trying to run the kernel.

 

 

Beginning the internship at OPW

This is my first post on this blog, where I will keep track of the many interesting things that I will work on during this internship.

For the beginning, I want to say that I am very happy for being accepted at Outreach Program for Women. All I wanted for this summer was to have the opportunity to work at the Linux Kernel and, with the help of this program, my wish came true.

I will work on RCU (Read-Copy-Update) and my mentor is Paul E. McKenney. More exactly the name of my project is “Automatically Locate RCU Abuses”.

So, what is RCU?
Read-Copy-Update is a reader-writer synchronization mechanism. It allows multiple readers which not contain any locks or atomic instructions (or memory barriers – although few architectures need them) and writers can update in the presence of readers! This is a very interesting feature.

Write-side critical sections maintain multiple versions of data structures in order to keep valid data for older and newer readers. If there is unnecessary data, the writers have a mechanism of deferring the destruction of that data. They could wait for a signal from a reader and delete it, but instead they wait until they have many signals from more readers and then gets rid of those operations. This is a good thing because it avoids the overhead of doing this after every read-side critical section.

For more information about it, I suggest the RCU Documentation and the interesting articles/papers on the Internet about it too 🙂

A tool that I will use throughout this internship is Coccinelle. Coccinelle is a very useful, powerful and time-saving tool. Coccinelle was created for helping the Linux Kernel. It matches and transforms the source code of C programs. You can rename functions, add new parameters to them or remove parameters and much more things, both simpler and more difficult. There are many examples on the Internet and if you are curious you could take a look.

Now, let’s discuss how I spent these internship days. I allocated some important time for RCU Documentation, Coccinelle documentation and examples of Coccinelle scripts. My mentor helped me having a better understanding of RCU and right now I am working at my first task. Also, he was very understanding with me because I have made a slow start due to my final exams.

Shortly, my first task assume to automatically replace (using Coccinelle) calls of the macro “rcu_assign_pointer” with “RCU_INIT_POINTER”. There are some cases where this thing could be done, but I have to be very careful because a wrong replacement leads to bad things (impossible to detect memory corruption).

• “rcu_assign_pointer” assigns a specified value to a specified RCU-protected pointer. It also inserts memory barriers to determine the compiler to not reorder the code that initializes the structure after the pointer assignment. It ensures that any concurrent RCU readers will see the initialization made before the assignment.
• “RCU_INIT_POINTER” assigns a specified value to a specified RCU-protected pointer, but it doesn’t have any memory barriers. It is useful when readers do not need any ordering constraints.

I have been looking of the usages of “rcu_assign_pointer” in the source tree and I started to think of how I will write the Coccinelle script.

In the next post, I will talk about the cases where these replacements could be done and my progress in this task.